﻿//ISBN号码（模拟）
//https://www.nowcoder.com/practice/95712f695f27434b9703394c98b78ee5?tpId=290&tqId=39864&ru=/exam/oj

//#include <iostream>
//using namespace std;

//int main() {
//    string s;
//    cin >> s;
//
//    int index = 1, n = s.size();
//    long long sum = 0;
//    for (int i = 0; i < n - 1; i++)
//    {
//        if (isdigit(s[i]))
//        {
//            sum += index * (s[i] - '0');
//            index++;
//        }
//    }
//
//    sum %= 11;
//
//    if (sum == s[n - 1] - '0' || sum == 10 && s[n - 1] == 'X')
//        cout << "Right" << endl;
//    else
//    {
//        s[n - 1] = (sum == 10 ? 'X' : sum + '0');
//        cout << s << endl;
//    }
//}


//kotori和迷宫（BFS/DFS）
//https://ac.nowcoder.com/acm/problem/50041

//#include<iostream>
//#include<cstring>
//#include<queue>
//
//using namespace std;
//
//const int N = 35;
//
//int x1, y1;//起点位置
//int n, m;
//char arr[N][N];
//int dist[N][N];//各点和起点的距离
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//queue<pair<int, int>> q;
//
//void bfs()
//{
//    memset(dist, -1, sizeof(dist));
//    dist[x1][y1] = 0;
//    q.push({ x1, y1 });
//
//    while (q.size())
//    {
//        auto [x2, y2] = q.front();
//        q.pop();
//        for (int i = 0; i < 4; i++)
//        {
//            int nx = x2 + dx[i], ny = y2 + dy[i];
//            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1 && arr[nx][ny] != '*')
//            {
//                dist[nx][ny] = dist[x2][y2] + 1;
//                if(arr[nx][ny]!='e')
//                    q.push({ nx,ny });
//            }
//        }
//    }
//}
//
//int main()
//{
// 
//    cin >> n >> m;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            cin >> arr[i][j];
//            if (arr[i][j] == 'k')
//            {
//                x1 = i;
//                y1 = j;
//            }
//        }
//    }
//
//    bfs();
//
//    int cnt = 0, lenth = 1e9;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            if (arr[i][j] == 'e' && dist[i][j] != -1)
//            {
//                cnt++;
//                lenth = min(lenth, dist[i][j]);
//            }
//        }
//    }
//    if (cnt == 0)
//        cout << -1 << endl;
//    else
//        cout << cnt << ' ' << lenth << endl;
//}


//矩阵最长递增路径（记忆化搜索）
//https://www.nowcoder.com/practice/7a71a88cdf294ce6bdf54c899be967a2?tpId=196&tqId=37184&ru=/exam/oj

//#include <vector>
//#include <iostream>
//
//using namespace std;
//
//class Solution {
//public:
//    int n, m;
//    int memo[1005][1005];
//    int dx[4] = { 0,0,1,-1 };
//    int dy[4] = { 1,-1,0,0, };
//
//    int dfs(vector<vector<int> >& matrix, int x, int y)
//    {
//        if (memo[x][y])
//            return memo[x][y];
//
//        int len = 1;
//        for (int i = 0; i < 4; i++)
//        {
//            int a = x + dx[i], b = y + dy[i];
//            if (a >= 0 && a < n && b >= 0 && b<m && matrix[a][b]>matrix[x][y])
//            {
//                len = max(len, 1 + dfs(matrix, a, b));
//            }
//        }
//        memo[x][y] = len;
//        return len;
//    }
//
//    int solve(vector<vector<int>>& matrix) {
//        n = matrix.size(), m = matrix[0].size();
//        memset(memo, 0, sizeof(memo));
//
//        int ret = 0;
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < m; j++)
//            {
//                ret = max(ret, dfs(matrix, i, j));
//            }
//        }
//        return ret;
//    }
//};